//
//  main.cpp
//  mergeSort
//
//  Created by Shane on 17/9/21.
//  Copyright © 2017年 Shane. All rights reserved.
//

#include <iostream>

void merge(int a[], int low, int middle, int high){
    int *tempArr = new int[high-low+1];
    
    
    int i = low, j = middle+1, k = 0;
    while (i <= middle && j <= high) {
        if (a[i] > a[j]) {
            tempArr[k++] = a[j++];
        }else{
            tempArr[k++] = a[i++];
        }
    }
    
    while (i <= middle) {
        tempArr[k++] = a[i++];
    }
    while (j <= high) {
        tempArr[k++] = a[j++];
    }
    
    for (i = low, k = 0; i <= high; k++, i++) {
        a[i] = tempArr[k];
    }
  
    
    delete [] tempArr;
    
}

void mergeSort(int a[], int low, int high){
    if (low < high) {
        int middle = (low + high) / 2;
        mergeSort(a, low, middle);
        mergeSort(a, middle+1, high);
        merge(a, low, middle, high);
        
    }
}



int main(int argc, const char * argv[]) {
    int a[] = {1,2,5,4,8,6,7,10,9,0,3};
    int count = sizeof(a)/sizeof(a[0]);
    mergeSort(a, 0, count-1);
    return 0;
}
